Many expert system problems, for example in the configuration-space, may require the use of a complex algorithm to help find solutions. Typical algorithms used to find solutions may often be either state-based algorithms, such as Rete algorithms, or backtracking-based algorithms. Each type of algorithm may have its advantages and disadvantages. For example, state-based algorithms may often tend to be heavy consumers of both memory and time for large systems. For this reason, backtracking-based algorithms may be considered to be better suited for solution finding within large systems.
Backtracking allows solutions to configuration space problems to be found by enumerating candidates at various choice points while building a system. As each choice is made in pursuit of a goal, a ‘search tree’ is formed. A new branch in the tree is created if a failure state is encountered and a previously chosen candidate is thrown away in favor of a new candidate. Not all candidates need to necessarily be evaluated to find a valid solution.